package com.ask.hash;

import java.util.BitSet;

public class BloomFilter {
    private final int size; // 位数组大小
    private final BitSet bitSet; // 位数组
    private final int hashCount; // 哈希函数个数

    public BloomFilter(int size, int hashCount) {
        this.size = size;
        this.bitSet = new BitSet(size);
        this.hashCount = hashCount;
    }

    // 简单哈希函数
    private int[] hash(String value) {
        int[] hashes = new int[hashCount];
        for (int i = 0; i < hashCount; i++) {
            hashes[i] = Math.abs(value.hashCode() + i * 31) % size;
        }
        return hashes;
    }

    // 添加元素
    public void add(String value) {
        int[] hashes = hash(value);
        for (int hash : hashes)
            bitSet.set(hash);
    }

    // 查询元素是否存在
    public boolean mightContain(String value) {
        int[] hashes = hash(value);
        for (int hash : hashes) {
            if (!bitSet.get(hash))
                return false; // 不存在
        }
        return true; // 可能存在
    }

    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(1000, 3);
        bloomFilter.add("hello");
        bloomFilter.add("world");

        System.out.println(bloomFilter.mightContain("hello")); // true
        System.out.println(bloomFilter.mightContain("world")); // true
        System.out.println(bloomFilter.mightContain("java"));  // false
    }

}


